package 数据结构专栏.B_链表专栏.training;

import 数据结构专栏.B_链表专栏.ListNode;
import 数据结构专栏.B_链表专栏.ListUtil;

/**
 * @Title 链表测试手写代码1
 * @Author zhengqiang.tan
 * @Date 2021/5/18 7:50 AM
 */
public class Test3_20240312 {
    public static void main(String[] args) {
        ListNode list = ListUtil.getList();
        System.out.println();
        ListUtil.printList(delDuplicate(list));
    }

    // 1. 删除重复项(0)
    public static ListNode delDuplicate(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        head.next = delDuplicate(head.next);
        if (head.val == head.next.val) {
            head = head.next;
        }
        return head;
    }

    // 2. 反转单链表(1) 使用递归写法
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode nextNode = head.next;
        head.next = null;
        ListNode res = reverseList(nextNode);
        nextNode.next = head;
        return res;
    }

    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next; // 保存下一个节点
            head.next = prev;
            prev = head;
            head = next; // 下一个待反转节点
        }
        return prev;
    }


    // 3. 删除链表指定节点
    public static void delListNode(ListNode node) {
        if (node == null || node.next == null) {
            return;
        }
        node.next = node.next.next;
        node.val = node.next.val;

    }


    // 4. 判断链表是否有环 (0)
    public static boolean hasLoop(ListNode n) {
        if (n == null || n.next == null) {
            return false;
        }
        ListNode p1 = n;
        ListNode p2 = n.next.next;

        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        if (p1 == null) return false;
        if (p1.val == p2.val) return true;


        return false;
    }

    // 2
    public static boolean hasLoop2(ListNode n) {
        ListNode fast = n;
        ListNode slow = n;

        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow.val == fast.val) {
                return true;
            }
        }

        return false;
    }


    // 5.合并两个已排序链表
    public static ListNode mergeList(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeList(l2.next, l1);
            return l2;
        }

    }


    // 6. 求链表倒数第K节点 (0) 双指针，非常简单
    // 面试题 02.02. 返回倒数第 k 个节点 https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
    public int kthToLast(ListNode head, int k) {
        ListNode pre = head, cur = head;
        for (int i = 0; i < k; i++) {
            cur = cur.next;
        }
        while (cur != null) {
            pre = pre.next;
            cur = cur.next;
        }
        return pre.val;
    }


    /**
     * 获取链表倒数第 K 个节点
     * @param head 链表的头节点
     * @param k 倒数的顺序，即要找到链表中倒数第 k 个节点
     * @return 返回链表中倒数第 k 个节点，如果链表长度小于 k，则返回 null
     */
    public static ListNode getKNode(ListNode head, int k) {

        // 处理链表为空或只有一个节点的情况
        if (head == null || head.next == null) {
            return head;
        }

        ListNode fast = head.next; // 快指针初始化为头节点的下一个节点
        ListNode slow = head.next; // 慢指针初始化为头节点的下一个节点
        int i;
        // 快指针先前进 k 步
        for (i = 0; i < k && fast != null; i++) {
            fast = fast.next;
        }

        // 如果快指针已经超出链表长度，则链表长度小于 k，返回 null
        if (i < k) return null;

        // 慢指针和快指针同时向后移动，直到快指针到达链表末尾
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // 返回慢指针指向的倒数第 k 个节点
        return slow;
    }

    // 7. 链表局部反转 （92. 反转链表 II ，难度为 中等)
    // 单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
    // 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
    public ListNode reverseBetween(ListNode head, int l, int r) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        r -= l;
        ListNode hh = dummy;
        while (l-- > 1) hh = hh.next;

        ListNode a = hh.next, b = a.next;
        while (r-- > 0) {
            ListNode tmp = b.next;
            b.next = a;
            a = b;
            b = tmp;
        }

        hh.next.next = b;
        hh.next = a;
        return dummy.next;
    }

}
